package Q239

import java.util.LinkedList

import java.util.Deque

fun main(){
    val arr: IntArray = intArrayOf(1,3,-1,-3,5,3,6,7)
    val k = 3
    val maxSlidingWindow = Solution().maxSlidingWindow(arr, k)
    for(i in maxSlidingWindow.indices){
        println(maxSlidingWindow[i])
    }
}

/**
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值
 */
class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        if (nums.size === 1) {
            return nums
        }
        val len: Int = nums.size - k + 1
        //存放结果元素的数组
        //存放结果元素的数组
        val res = IntArray(len)
        var num = 0
        //自定义队列
        //自定义队列
        val myQueue = MyQueue()
        //先将前k的元素放入队列
        //先将前k的元素放入队列
        for (i in 0 until k) {
            myQueue.add(nums[i])
        }
        res[num++] = myQueue.peek()
        for (i in k until nums.size) {
            //滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
            myQueue.poll(nums[i - k])
            //滑动窗口加入最后面的元素
            myQueue.add(nums[i])
            //记录对应的最大值
            res[num++] = myQueue.peek()
        }
        return res
    }
}

class MyQueue {
    var deque: Deque<Int> = LinkedList()

    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    //同时判断队列当前是否为空
    fun poll(`val`: Int) {
        if (!deque.isEmpty() && `val` == deque.peek()) {
            deque.poll()
        }
    }

    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    fun add(`val`: Int) {
        while (!deque.isEmpty() && `val` > deque.last) {
            deque.removeLast()
        }
        deque.add(`val`)
    }

    //队列队顶元素始终为最大值
    fun peek(): Int {
        return deque.peek()
    }
}